/*
 * @lc app=leetcode.cn id=417 lang=typescript
 *
 * [417] 太平洋大西洋水流问题
 */

// @lc code=start
function pacificAtlantic(heights: number[][]): number[][] {
  const m = heights.length;
  const n = heights[0].length;
  const dirs = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];
  // 标记访问过的点
  const visited = Array(m)
    .fill(0)
    .map(() => Array(n).fill(0));

  // type表示 1: pacific, 2: atlantic
  const dfs = (i: number, j: number, type: number) => {
    // 表示已经被当前type的洋流访问过了
    if ((visited[i][j] & type) !== 0) return;
    visited[i][j] |= type;
    // 两个洋流都能访问到，放入答案中
    if (visited[i][j] === 3) {
      ans.push([i, j]);
    }
    for (const [di, dj] of dirs) {
      const x = i + di;
      const y = j + dj;
      // 越界
      if (x < 0 || x >= m || y < 0 || y >= n) continue;
      // 我们是从终点往起点搜索，所以是从低向高找
      if (heights[x][y] < heights[i][j]) continue;
      dfs(x, y, type);
    }
  };
  const ans: number[][] = [];

  // 从每个边界点开始深搜
  for (let i = 0; i < m; i++) {
    // 第一列
    dfs(i, 0, 1);
    // 最后一列
    dfs(i, n - 1, 2);
  }
  for (let j = 0; j < n; j++) {
    // 第一行
    dfs(0, j, 1);
    // 最后一行
    dfs(m - 1, j, 2);
  }

  return ans;
}
// @lc code=end
